//使用容器版本
class Solution {
public:
    int totalFruit(vector<int>& fruits) 
    {
        int left = 0, right = 0,ret = 0, sz = fruits.size();
        unordered_map<int,int> hs;
        for(right = 0; right < sz; right++)
        {
            //进窗口
            hs[fruits[right]]++;

            //判断
            while(hs.size() > 2)
            {
                //出窗口
                hs[fruits[left]]--;
                if(hs[fruits[left]] == 0)
                    hs.erase(fruits[left]);
                
                left++;
            }
            //更新结果
            ret = max(ret,right - left + 1);
        }

        return ret;
    }
};

//数组模拟哈希表的版本，可以进一步降低时间复杂度
class Solution {
public:
    int totalFruit(vector<int>& fruits) 
    {
        int left = 0, right = 0,ret = 0, kind = 0;
        int hs[100001] = {0};
        for(right = 0; right < fruits.size(); right++)
        {
            //进窗口
            if(hs[fruits[right]] == 0)
                kind++;

            hs[fruits[right]]++;

            //判断
            while(kind > 2)
            {
                //出窗口
                hs[fruits[left]]--;
                if(hs[fruits[left]] == 0)
                    kind--;
                
                left++;
            }
            //更新结果
            ret = max(ret,right - left + 1);
        }

        return ret;
    }
};

class Solution {
public:
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> st;
        for(auto& str : tokens){
            if(str == "+" || str == "-" ||
                str == "*" || str == "/"){
                int right = st.top();
                st.pop();

                int left = st.top();
                st.pop();

                switch(str[0]){
                    case '+':
                        st.push(left+right);
                        break;
                   case '-':
                        st.push(left-right);
                        break;
                   case '*':
                        st.push(left*right);
                        break;
                   case '/':
                        st.push(left/right);
                         break;}
            }
            else
                st.push(stoi(str));
        }
        return st.top();
    }
};

class MinStack {
public:
    void push(int val) {
        _st.push(val);

        if(_minst.empty() || val <= _minst.top())
            _minst.push(val);
    }
    
    void pop() {
        if(_st.top() == _minst.top())
            _minst.pop();
            
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }

private:
    stack<int> _st;
    stack<int> _minst;
};
bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
{
    stack<int> st;
    int pushi = 0, popi = 0;

    while(pushi < pushV.size())
    {
        //入栈序列元素入栈
        st.push(pushV[pushi++]);

        //判断是否匹配出栈序列
        while(!st.empty() && st.top() == popV[popi])
        {
            st.pop();
            popi++;
        }
    }
    return st.empty();
}

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            ret ^= nums[i];
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> generate(int numRows) 
    {
        vector<vector<int>> vv;
        vv.resize(numRows);
        for(int i = 0; i < numRows; i++)
        {
            vv[i].resize(i+1,0);
            vv[i][0] = vv[i][i] = 1;
            for(int j = 1; j < i; j++)
            {
                vv[i][j] = vv[i-1][j-1] + vv[i-1][j];
            }
        }
        return vv;
    }
};
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        int left = 0, right = 1;
        while(right < nums.size())
        {
            if(nums[left] == nums[right])
            {
                right++;
            }
            else
            {
                nums[++left] = nums[right++];
            }
        }
        return left + 1;
    }
};
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        //用于保存所有元素异或的和
        int sum = 0;
        for(auto e : nums)
        {
            sum ^= e;
        }
        //因为sum = x1 + x2
        // 防止溢出
        int lsb = (sum == INT_MIN ? sum : sum & (-sum));
        int x1,x2 = 0;
        //利用任何数异或1都等于这个数本身
        for(auto e : nums)
        {
            if(e & lsb)
                x1 ^= e;
            else
                x2 ^= e;
        }

        return {x1,x2};
    }
};
